package lib.random;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

/**
 * Extends the capabilities of class Random
 * @author dolphinigle
 */
public class ExtendedRandom extends Random {
  private static final long serialVersionUID = 7526473296623776147L;

  /**
   * Equivalent to Random, but with extended capabilities
   * @param seed
   */
  public ExtendedRandom(long seed) {
    super(seed);
  }
  
  /**
   * Constructor with current time as seed.
   */
  public ExtendedRandom() {
    this(System.currentTimeMillis());
  }

  /**
   * Generates a random non-negative integer within its value
   * @return a positive integer within the 2^32 limit of an integer
   */
  public int nextNonNegativeInt() {
    int value;
    while ((value = this.nextInt()) < 0) {}
    return value;
  }

  /**
   * Generates a random non-negative long within its value
   * @return a positive long within the 2^64 limit of a long
   */
  public long nextNonNegativeLong() {
    long value;
    while ((value = this.nextLong()) < 0L) {}
    return value;
  }

  /**
   * Generates a random int with bounded possible values
   * @param lbound lower bound of the returned value, inclusive
   * @param ubound upper bound of the returned value, inclusive
   * @return a number strictly between lbound and ubound, at random
   */
  public int nextInt(int lbound, int ubound) {
    assert lbound <= ubound;
    return this.nextNonNegativeInt() % (ubound - lbound + 1) + lbound;
  }

  /**
   * Generates a random long with bounded possible values
   * @param lbound lower bound of the returned value, inclusive
   * @param ubound upper bound of the returned value, inclusive
   * @return a number strictly between lbound and ubound, at random
   */
  public long nextLong(long lbound, long ubound) {
    assert lbound <= ubound;
    return this.nextNonNegativeLong() % (ubound - lbound + 1L) + lbound;
  }

  /**
   * Generates a random double with bounded possible values
   * @param lbound minimum possible value returned, inclusive
   * @param ubound exclusive upperbound on the value, EXCLUSIVE
   * @return a number between lbound (inclusive) and ubound (exclusive) at
   *         random
   */
  public double nextDouble(double lbound, double ubound) {
    assert lbound <= ubound;
    return lbound + this.nextDouble() * (ubound - lbound);
  }

  /**
   * Generates an array of integers the values of whose element is bounded
   * @param number_of_elements the number of elements in the array generated
   * @param lbound each element of the returned array will not be smaller than
   * this
   * @param ubound each element of the returned array will not be larger that
   * this
   * @param is_distinct true iff returned array contains no identical integers
   * @return an array of integers
   */
  public int[] nextArrayInt(int number_of_elements,
          int lbound, int ubound, boolean is_distinct) {

    assert (number_of_elements >= 0);
    
    assert (lbound <= ubound);

    // assert that sufficient number of elements is present if is_distinct is
    // enforced
    assert (!is_distinct || number_of_elements <= (ubound - lbound + 1));

    int[] ret = new int[number_of_elements];
    long[] res = this.nextArrayLong(number_of_elements, (long)lbound,
            (long)ubound, is_distinct);
    for (int i = 0; i < res.length; ++i) {
      ret[i] = (int)res[i];
    }
    return ret;
  }

  /**
   * Generates an array of longs the values of whose element is bounded
   * @param number_of_elements the number of elements in the array generated
   * @param lbound each element of the returned array will not be smaller than
   * this
   * @param ubound each element of the returned array will not be larger that
   * this
   * @param is_distinct true iff returned array contains no identical longs
   * @return an array of longs
   */
  public long[] nextArrayLong(int number_of_elements,
          long lbound, long ubound, boolean is_distinct) {

    assert (number_of_elements >= 0);

    assert (lbound <= ubound);

    // assert that sufficient number of elements is present if is_distinct is
    // enforced
    assert (!is_distinct || number_of_elements <= (ubound - lbound + 1));

    long[] ret = new long[number_of_elements];
    Set<Long> set = new TreeSet<Long>();

    for (int i = 0; i < number_of_elements; ++i) {
      long number = this.nextLong(lbound, ubound);
      if (is_distinct && set.contains(Long.valueOf(number))) {
        // already exists
        // retry
        --i;
        continue;
      }

      ret[i] = number;

      if (is_distinct) {
        set.add(Long.valueOf(number));
      }
    }
    return ret;
  }

  /**
   * Generates an array of longs the values of whose element is bounded and
   * no identical consecutive element is present
   * @param number_of_elements the number of elements in the array generated
   * @param lbound each element of the returned array will not be smaller than
   * this
   * @param ubound each element of the returned array will not be larger that
   * this
   * @param is_distinct true iff returned array contains no identical longs
   * @return an array of longs
   */
  public long[] nextNonIdentialConsecutiveArrayLong(int number_of_elements,
          long lbound, long ubound, boolean is_distinct) {

    assert (number_of_elements >= 0);

    assert (lbound <= ubound);

    // assert that sufficient number of elements is present if is_distinct is
    // enforced
    assert (!is_distinct || number_of_elements <= (ubound - lbound + 1));

    long[] ret = new long[number_of_elements];
    Set<Long> set = new TreeSet<Long>();

    for (int i = 0; i < number_of_elements; ++i) {
      long number = this.nextLong(lbound, ubound);
      if (is_distinct && set.contains(Long.valueOf(number))) {
        // already exists
        // retry
        --i;
        continue;
      }

      if (i > 0 && ret[i-1] == number) {
        // identical element
        --i;
        continue;
      }

      ret[i] = number;

      if (is_distinct) {
        set.add(Long.valueOf(number));
      }
    }
    return ret;
  }

  /**
   * Picks a random set of distinct integers from a set of consecutive integers
   *
   * @param number_of_items number of available items to be chosen, numbered
   * 0..number_of_items - 1
   * @param number_of_chosen number of items to be chosen
   * @return an array of integer containing number_of_chosen items which
   * are the number of items picked given in an ascending order
   */
  public int[] nextCombination(int number_of_items, int number_of_chosen) {

    assert (number_of_items >= 0);
    assert (number_of_chosen >= 0);
    assert (number_of_items >= number_of_chosen);

    ArrayList<Integer> items = new ArrayList<Integer>();

    // Strategy Pattern

    double algo1_complexity = (double)number_of_items;
    double algo2_complexity = (double)number_of_chosen *
            (double)number_of_chosen *
            Math.log(number_of_chosen) /
            Math.log(2);

    if (algo1_complexity < algo2_complexity) {
      // use first algorithm that works in O(number_of_items)

      for (int i = 0; i < number_of_items; ++i) {
        // test if this item should be inserted
        int random_val = this.nextInt(number_of_items - i);
        if (random_val < number_of_chosen - items.size()) {
          // picked
          items.add(Integer.valueOf(i));
        }
      }
    } else {
      // use second algorithm that works in O(number_of_chosen *
      // number_of_chosen * log2(number_of_chosen)

      for (int i = 0; i < number_of_chosen; ++i) {
        int picked = this.nextInt(number_of_items - i);
        for (Integer num : items) {
          if (num <= picked) {
            ++picked;
          }
        }
        items.add(Integer.valueOf(picked));
        Collections.sort(items);
      }
    }

    int[] ret = new int[number_of_chosen];
    for (int i = 0; i < items.size(); ++i) {
      ret[i] = items.get(i);
    }
    return ret;
  }

  /**
   * Generates a partition of number_to_be_partitioned into non-negative
   * integers.
   * <br/><br/>
   * There are no strict ordering of the output and different order is
   * considered to be different output. I.e., if the number is represented
   * as a sequence of number_to_be_partitioned integers, then the numbers
   * are all distinct and we want to find the number of ways to partition
   * these numbers into number_of_partitions partitions such that all numbers
   * inside each partition are consecutive
   *
   * @param number_to_be_partitioned the number such that the sum of every
   * partition is equal to this number
   * @param number_of_partitions the number of partitions
   * @param not_zero true iff no zero may occur in the partition
   * @return an array containing number_of_partitions element which represents
   * the partitions and its ordering
   */
  public int[] nextAsymmetricPartition(int number_to_be_partitioned,
          int number_of_partitions,
          boolean not_zero) {

    assert (number_to_be_partitioned >= 0);
    assert (number_of_partitions >= 1);
    assert (!not_zero || number_to_be_partitioned >= number_of_partitions);

    if (not_zero) number_to_be_partitioned -= number_of_partitions;

    int all_choices = number_to_be_partitioned + number_of_partitions - 1;
    int picks = number_of_partitions - 1;
    int[] combin = this.nextCombination(all_choices, picks);

    int last = -1;
    int[] ret = new int[number_of_partitions];
    
    for (int i = 0; i < combin.length; ++i) {
      ret[i] = combin[i] - last - 1;
      last = combin[i];
    }

    ret[number_of_partitions - 1] = all_choices - last - 1;

    if (not_zero) {
      for (int i = 0; i < ret.length; ++i) ret[i]++;
    }

    return ret;
  }

  /**
   * Shuffles an array at random. Modifies the original input array
   * @param param An array to be shuffled
   */
  public <T> void nextShuffle(T[] param) {
    ArrayList<T> alt = new ArrayList<T>();
    alt.addAll(Arrays.asList(param));
    Collections.shuffle(alt, this);
    alt.toArray(param);
  }

  /**
   * Shuffles an array at random. Modifies the original input array
   * @param param An array to be shuffled
   */
  void nextShuffle(int[] param) {
    ArrayList<Integer> alt = new ArrayList<Integer>();
    for (int i : param) alt.add(i);
    Collections.shuffle(alt, this);
    for (int i = 0; i < param.length; ++i) {
      param[i] = alt.get(i);
    }
  }
  
  /**
   * Generates a random string from a given alphabet.
   * @param n String length
   * @param alphabets
   * @param is_distinct
   */
  public String nextString(int n, String alphabets, boolean is_distinct) {
    if (n == 0) {
      return "";
    }
    assert alphabets.length() > 0;
    if (is_distinct && alphabets.length() < n) {
      assert false;
    }
    int[] picked = this.nextArrayInt(n, 0, alphabets.length() - 1, is_distinct);
    char[] ret = new char[n];
    for (int i = 0; i < picked.length; ++i) {
      ret[i] = alphabets.charAt(picked[i]);
    }
    return String.valueOf(ret);
  }

  /**
   * Retrieves a random character from a string
   */
  public char nextChar(String alphabets) {
    return alphabets.charAt(this.nextInt(0, alphabets.length()-1));
  }
}
